/* 
	Grupo 2

	Alunos: 
		Luis Felipe Souza de Mattos   RA: 107822
	
		Debora Maia Silva 	      RA: 101985

Objetivo do programa: montar listas simples e duplamente encadeadas e circulares de n elementos e com elas 
resolver o problema de josephus de, nas listas, 'matar' n-1 pessoas pulando em 'm' posicoes por vez.*/

#include <stdio.h>
#include <stdlib.h>
#include "lista.h"
#include "josephus.h"

/* funcao que mata 'n - 1' pessoas de 'm' em 'm' pessoas ate restar somente 1 sobrevivente em
uma lista duplamente encadeada */
int MataDuplo(ListaDupla **inicio, int n, int m,char sentido)
{
	ListaDupla *lixo;
	ListaDupla *aux;
	int i,j,sobrevive;
 
	lixo = (*inicio);
	aux=(*inicio);
 
	for (i=0;i<n-1;i++)
	{
	   /* atualiza o ponteiro da posicao atual */
	   if (sentido == 'h')
	      aux=lixo->hor;
	   else if (sentido == 'a')
	      aux=lixo->antihor;
	/* conecta o elemento anterior com o seguinte */
	   lixo->antihor->hor=lixo->hor;
	   lixo->hor->antihor=lixo->antihor;
	/* mata o atual */
	   free(lixo);
	/* atualiza o ponteiro do elemento a ser morto */
	   lixo=aux;
	/* move o ponteiro a ser morto para a proxima posicao */
	   for (j=0;j<m;j++)
	   {
	      if (sentido == 'h') 
	         lixo=lixo->hor;
	      else if (sentido == 'a')
		 lixo = lixo->antihor;
	   }
	}
	sobrevive = aux->pessoa;
	/* libera a memoria do sobrevivente */
	free(aux);
	/* retorna o numero do sobrevivente */
	return sobrevive;
}

/* funcao que mata n - 1 pessoas de m em m pessoas ate restar somente 1 sobrevivente em
uma lista simples */
int MataSimples(ListaSimples **inicio, int n, int m)
{
	ListaSimples *ultimo, *aux, *lixo;
	int i,j,sobrevive;
             
	/* inicializa os ponteiros */
	ultimo = *inicio;
	aux = *inicio;
	lixo = *inicio;
               
	for (i=0;i<n-1;i++)
	{
	   aux = lixo -> prox;
	   /* procura o elemento anterior a celula que vai ser removida */
	   while(ultimo->prox != lixo)
	      ultimo = ultimo->prox;	
	   /* conecta o elemento anterior a celula ao seguinte */
	   ultimo->prox = aux;		
	   /* mata a celula */
	   free(lixo);
	   /* atualiza os ponteiros */
	   lixo = aux;
	   ultimo = aux;
	   /* move o ponteiro para a proxima posicao a ser removida */
	   for (j = 0;j < m;j++)
	      lixo = lixo->prox;
	}
        sobrevive = aux->pessoa;
	/* libera a memoria do sobrevivente */
	free(aux);
	/* retorna o numero do sobrevivente */
	return sobrevive;
}

int josephus_duplo(char sentido, int n, int m)
{
	ListaDupla *inicio;

	/* caso nao tenha pessoas a matar, retornar zero */
	if(n == 0)
	   return 0;
 	
	/* monta a lista dupla */
	MontaListaDupla(&inicio,n);
 
	/* retorna o numero do sobrevivente */
	return MataDuplo(&inicio,n,m,sentido);
}

int josephus_simples(int n, int m)
{
	ListaSimples *inicio;

	/* caso nao tenha pessoas a matar, retornar zero */
	if (n == 0)
	   return 0;
 
	/* monta a lista simples */
	MontaListaSimples(&inicio,n);

	/* retorna o numero do sobrevivente */
	return MataSimples(&inicio,n,m);
}
